package com.xyhuo.leetcode.december;

import com.xyhuo.leetcode.common.ListNode;

/**
 * 分隔链表
 * https://leetcode.cn/problems/partition-list/
 *
 * @time 2023/12/29
 */
public class Partition {

//    public static void main(String[] args) {
//        Partition p = new Partition();
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(4);
//        ListNode l3 = new ListNode(3);
//        ListNode l4 = new ListNode(2);
//        ListNode l5 = new ListNode(5);
//        ListNode l6 = new ListNode(2);
//
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;
//        l5.next = l6;
//        p.partition(l1, 3);
//    }

    public ListNode partition(ListNode head, int x) {
        ListNode zero = new ListNode();
        zero.next = head;
        ListNode left = zero, lastNode = zero, right = head;
        while (right != null && right.val < x) {
            lastNode = right;
            left = right;
            right = right.next;
        }
        while (right != null) {
            while (right != null && right.val >= x) {
                lastNode = right;
                right = right.next;
            }
            if (right != null) {
                lastNode.next = right.next;
                right.next = left.next;
                left.next = right;
                left = left.next;
                right = lastNode.next;
            }
        }
        return zero.next;

    }
}
